package com.text.dp;

/**
 * Created by mu on 2017/7/27.
 */
public class LongSequence {

    public static void main(String[] args) {
     //   longDiscontinuousSequence(8);
        longContinuousSequence(8);
    }
    /**
     * 给定一个数组，查找其最长 连续 子序列
     */
    private static void longContinuousSequence(int arrLen) {
        int [] dp=new int [arrLen];
        int[] arr=new int[]{3,2,7,7,8,6,4,8,4};
        int max=0;
        int i,j;
        for(i=0;i<arrLen;i++){
            dp[i]=1;
        }
        for(i=0;i<arrLen-1;i++){
            if(arr[i]<arr[i+1]){
                dp[i+1]=dp[i]+1;
                if(dp[i+1]>max)
                    max=dp[i+1];
            }
        }
        System.out.println(max);
    }


    /**
     * 给定一个数组，查找其最长 非连续 子序列
     */
    private static void longDiscontinuousSequence(int arrLen) {
        int[] dp=new int [arrLen];
        int[] arr=new int[]{3,2,5,5,4,3,2,9};//待判断的数组

        int i,j;
        int max=0;
        for(i=0;i<arrLen;i++){
            dp[i]=1;
            for(j=0;j<i;j++){
                if(arr[i]>arr[j]&&dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                    if(dp[i]>max)
                        max=dp[i];
                }
            }
        }
        System.out.println(max);
    }
}
